package com.javabasic.algorithm.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author xiongmin
 * @Description //TODO
 * @Date 2020/1/31 20:52
 * @Version 1.0
 **/
public class Permutations {

    /**
     * 解法一： 使用next_permutation 原理
     * @param nums
     * @return
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        toResult(result, nums);
        while (has_next_permutation(nums)) {
            toResult(result, nums);
        }
        return result;
    }

    private void toResult(List<List<Integer>> result, int[] nums) {
        ArrayList<Integer> integers = new ArrayList<>();
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            integers.add(nums[i]);
        }
        result.add(integers);
    }

    public boolean has_next_permutation(int[] nums) {
        int len = nums.length;

        for (int i = len - 1; i > 0; i--) {
            if (nums[i] > nums[i - 1]) {
                for (int j = len - 1; j >= 0; j--) {
                    if (nums[j] > nums[i - 1]) {
                        int temp = nums[i - 1];
                        nums[i - 1] = nums[j];
                        nums[j] = temp;
                        for (int p = i, q = len - 1; p < q; p++, q--) {
                            temp = nums[p];
                            nums[p] = nums[q];
                            nums[q] = temp;
                        }
                        return true;
                    }
                }
            }

        }
        return false;
    }

    /**
     * 解法二：
     * 其实这个全排列算法就是固定一个数的位置(left)，然后从下一位数再开始全排列(递归过程)...直到最后一位数，
     * 模拟手动全排列的过程。所以如果要去重的话，只要控制每次排列时，固定的那个数是不一样的就行了。因为固定的数不一样，
     * 那从这个数开始产生的全排列就不一样。所以只要让每次的left位置的数不一样就行，所以先sort，保证只有相邻的数是可能一样的，
     * 然后if (i != left && nums[left] == nums[i]) continue;使得每次固定的数(即left)都不一样，就行了。
     */
//    vector<vector<int>> permuteUnique(vector<int>& nums) {
//        sort(nums.begin(), nums.end());
//        perm(nums, 0, nums.size() - 1);
//        return ans;
//    }
//
//    void perm(vector<int> nums, int left, int right) {
//        if (left == right)
//            ans.push_back(nums);
//        else {
//            for (int i = left; i <= right; i++) {
//                if (i != left && nums[left] == nums[i]) continue;  # 去重
//                swap(nums[left], nums[i]);
//                perm(nums, left + 1, right);
//            }
//        }
//    }
}
